import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : xwj
 * @date : 2021/9/16 22:22
 * @description : 给你一个链表数组，每个链表都已经按升序排列。
 *                请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * @class : test23
 **/

public class test23 {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //1. 100 ms	40.2 MB
    //将数组中的元素一次遍历，合并到第一个元素中，暴力破解
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }

        ListNode res = lists[0];

        for (int i = 1; i < lists.length; i++) {
            res = mergerTwoListNode(res, lists[i]);
        }
        return res;
    }

    public static ListNode mergerTwoListNode(ListNode n1, ListNode n2) {
        ListNode pHead = new ListNode(0);
        ListNode pre = pHead;

        while (n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                pre.next = n1;
                n1 = n1.next;
            } else {
                pre.next = n2;
                n2 = n2.next;
            }
            pre = pre.next;
        }
        pre.next = n1 == null ? n2:n1;

        return pHead.next;
    }

    //2. 3 ms	40.1 MB
    //将数组进行遍历，两个一对合并，再将新得到的数组循环执行，直到数组中只剩一个元素
    public static ListNode mergeKLists2(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        List<ListNode> ls = Arrays.asList(lists);
        int len  = ls.size();
        while (len > 1) {
            List<ListNode> tmp = new ArrayList<>();

            for (int i = 0; i < len;) {
                ListNode t = mergerTwoListNode(ls.get(i), ls.get(i + 1));
                tmp.add(t);
                i = i + 2;
                if (len - i == 1) {
                    tmp.add(ls.get(i));
                    break;
                }
            }
            ls = tmp;
            len = ls.size();
        }
        return ls.get(0);
    }

    public static void main(String[] args) {
        ListNode tail = new ListNode(3);
        ListNode tmp = new ListNode(2, tail);
        ListNode head = new ListNode(1, tmp);

        ListNode tail1 = new ListNode(3);
        ListNode tmp1 = new ListNode(2, tail1);
        ListNode head1 = new ListNode(1, tmp1);

        ListNode[] nodes = new ListNode[]{head, head1};
        ListNode n = mergeKLists2(nodes);

        while (n != null) {
            System.out.println(n.val);
            n = n.next;
        }
    }

}
